package com.company.ljh.easy;
/**
 * 统计一个数字在排序数组中出现的次数
 */

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2022/6/7 9:20
 * @version:1.0
 */
public class 在排序数组中查找数字I {
    /**
     * 二分法查找
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int index = midleSearch(nums,target,0,nums.length - 1);
        int size = 1;
        if (index == -1){
            return 0;
        }else{
            int start = index-1;
            int end = index+1;
            while(start >= 0 && end < nums.length){
                if(nums[start--] == target){
                    size++;
                }else{
                    start = -1;
                }
                if(nums[end++] == target){
                    size++;
                }else{
                    end = nums.length;
                }
            }
            while(start >= 0 ){
                if(nums[start--] == target){
                    size++;

                }else{
                    start = -1;
                }
            }
            while( end < nums.length){
                if(nums[end++] == target){
                    size++;

                }else{
                    end = nums.length;
                }
            }
        }
        return size;
    }
    private int midleSearch(int []nums,int target,int start,int end){
        if(nums.length == 0){
            return -1;
        }
        if(start >= end){
            if(nums[start] == target){
                return start;
            }else{
                return -1;
            }
        }
        int middle = (end - start) /2 + start;
        if(nums[middle] > target){
            return midleSearch(nums,target,start,middle -1);
        }else if(nums[middle] < target){
            return midleSearch(nums,target,middle +1,end);
        }else{
            return middle;
        }
    }
}
